package string;

/**
 * @description:
 * @author: w_jingbo
 * @date: 2023/9/14
 * @Copyright: 博客：http://coisini.wang
 */
public class longestPalindrome {

    public static void main(String[] args) {
        String str = "abccbba" ;
        String str1 = "abbac" ;
        String str2 = "abaca" ;
        System.out.println(longestPalindrome2(str));
    }

    /**
     * 动态规划
     * @param s
     * @return
     */
    public static String longestPalindrome1(String s) {
        if(s == null || s.length() < 2){
            return s ;
        }
        int strLen = s.length() ;
        int maxStart = 0 ;
        int maxEnd = 0 ;
        int maxLen = 1 ;

        boolean[][] dp = new boolean[strLen][strLen] ;

        for(int r = 1 ; r < strLen ; r++){
            for(int l = 0 ; l < r ; l++){
                if(s.charAt(l) == s.charAt(r) && ((r - l <= 2) || dp[l+1][r-1])){
                    dp[l][r] = true;
                    if(r - l + 1> maxLen){
                        maxStart = l ;
                        maxEnd = r ;
                        maxLen = r - l + 1;
                    }
                }
            }
        }
        return s.substring(maxStart,maxEnd+1) ;
    }

    /**
     * 中心扩展法(在每个i位置去左/右/左右去扩展，找到最大子串)
     * @param s
     * @return
     */
    public static String longestPalindrome2(String s) {
        if(s == null || s.length() < 2){
            return s ;
        }
        int strLen = s.length() ;
        int maxLen = 0;
        int left = 0 ;
        int right = 0 ;
        int maxStart = 0 ;
        int len = 1;

        for (int i = 0; i < strLen; i++) {
            left = i - 1 ;
            right = i + 1 ;
            //向左扩散
            while(left >= 0 && s.charAt(left) == s.charAt(i)){
                len++;
                left--;
            }
            //向右扩散
            while(right < strLen && s.charAt(right) == s.charAt(i)){
                len++;
                right++;
            }
            //向两边同时扩散
            while(left >= 0 && right < strLen && s.charAt(left) == s.charAt(right)){
                len += 2;
                left--;
                right++;
            }
            if(len > maxLen){
                maxLen = len ;
                maxStart = left + 1;
            }
            len = 1 ;
        }
        return s.substring(maxStart,maxLen + maxStart) ;

    }
}
